package leetcode_800;

/**
 *@author 周杨
 *MyCalendarII_731 还是日历订购的问题 但是允许重复订两次元素 不能订3次
 *describe:修改线段树的方法  增加合并的规则 AC 89%
 *2018年10月14日 下午6:37:56
 */
public class MyCalendarII_731 {
	private static class SegmentTreeNode {
	    int l, r;
	    int k, lazy;
	    SegmentTreeNode left, right;
	        
	    SegmentTreeNode(int l, int r, int k) {
	        this.l = l;
	        this.r = r;
	        this.k = k;
	        this.lazy = 0;
	        this.left = this.right = null;
	    }
	}

	private int query(SegmentTreeNode node, int i, int j) {
	    normalize(node);
	    
	    if (i > j || node == null || i > node.r || j < node.l) return 0;
	    
	    if (i <= node.l && node.r <= j) return node.k;
	        
	    return Math.max(query(node.left, i, j), query(node.right, i, j));
	}

	private void update(SegmentTreeNode node, int i, int j, int val) {
	    normalize(node);
	        
	    if (i > j || node == null || i > node.r || j < node.l) return;
	    
	    if (i <= node.l && node.r <= j) {
	        node.lazy = val;
	        normalize(node);
	        return;
	    }
	        
	    update(node.left, i, j, val);
	    update(node.right, i, j, val);
	    
	    node.k = Math.max(node.left.k, node.right.k);
	}

	private void normalize(SegmentTreeNode node) {
	    if (node.lazy > 0) node.k += node.lazy;
	    
	    if (node.l < node.r) {
	        if (node.left == null || node.right == null) {
	            int m = node.l + (node.r - node.l) / 2;
	            node.left = new SegmentTreeNode(node.l, m, node.k);
	            node.right = new SegmentTreeNode(m + 1, node.r, node.k);
	        
	        } else if (node.lazy > 0) {
	            node.left.lazy += node.lazy;
	            node.right.lazy += node.lazy;
	        }
	    }
	    
	    node.lazy = 0;
	}


	SegmentTreeNode root;

	public MyCalendarII_731() {
	    root = new SegmentTreeNode(0, 1_000_000_000, 0);
	}

	public boolean book(int start, int end) {
	    int k = query(root, start, end - 1);
	    if (k >= 2) return false;
	    
	    update(root, start, end - 1, 1);
	    return true;
	}
}
